﻿using System.Collections.Generic;
using UnityEngine.Profiling;

namespace JH
{
    public static class ListExtensions
    {
        /// <summary>
        /// 对List进行原地快速排
        /// </summary>
        /// <typeparam name="T">元素类型</typeparam>
        /// <typeparam name="TComparer">比较器类型</typeparam>
        /// <param name="list">要排序的List</param>
        /// <param name="comparer">比较器实例</param>
        public static void QuickSort<T, TComparer>(this List<T> list, TComparer comparer)
            where TComparer : IComparer<T>
        {
            // 如果List为空或元素数小于2，则无需排序
            if (list == null || list.Count < 2)
                return;

            // 调用递归快排
            QuickSort(list, 0, list.Count - 1, comparer);
        }

        /// <summary>
        /// 递归快排实现
        /// </summary>
        private static void QuickSort<T, TComparer>(List<T> list, int left, int right,
            TComparer comparer)
            where TComparer : IComparer<T>
        {
            // 快排的递归出口：区间为空或只有一个元素时结束
            if (left >= right)
                return;

            // 分区操作，返回基准点的最终位置
            int pivotIdx = Partition(list, left, right, comparer);

            // 对基准点左侧子区间递归快排
            QuickSort(list, left, pivotIdx - 1, comparer);

            // 对基准点右侧子区间递归快排
            QuickSort(list, pivotIdx + 1, right, comparer);
        }

        /// <summary>
        /// 分区函数，将小于等于pivot的元素移到左边，大于的移到右边
        /// </summary>
        private static int Partition<T, TComparer>(List<T> list, int left, int right,
            TComparer comparer)
            where TComparer : IComparer<T>
        {
            // 选取区间最右边元素作为基准（pivot）
            T pivot = list[right];
            int i = left - 1; // i指向小于等于pivot的最后一个元素位置

            // 遍历区间[left, right-1]，将小于等于pivot的元素交换到前面
            for (int j = left; j < right; j++)
            {
                // 用struct比较器比较当前元素和pivot
                if (comparer.Compare(list[j], pivot) <= 0)
                {
                    i++; // 小于等于pivot的元素计数+1
                    Swap(list, i, j); // 把当前元素交换到前面
                }
            }

            // 最后把pivot放到中间（i+1）的位置
            Swap(list, i + 1, right);

            // 返回pivot的最终索引
            return i + 1;
        }

        /// <summary>
        /// 交换List中的两个元素
        /// </summary>
        private static void Swap<T>(List<T> list, int i, int j)
        {
            // 如果是同一个位置就不交换
            if (i == j) return;

            // 交换i和j位置的元素
            (list[i], list[j]) = (list[j], list[i]);
        }
    }
}